/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        //利用哈希表存储新节点和旧节点
        unordered_map<Node*, Node*> um;
        Node* cur = head;
        //利用新节点存储旧节点的值
        while (cur != nullptr) {
            um[cur] = new Node(cur->val);
            cur = cur->next;
        }

        //利用旧节点的next和random来填入到新节点的next和random
        cur = head;
        while (cur != nullptr) {
            um[cur]->next = um[cur->next];
            um[cur]->random = um[cur->random];
            cur = cur->next;
        }
        return um[head];
    }
};